#include "BTreeNode.h"
#include <stdlib.h>

using namespace std;

// LEAF: helper macros
#define entrySize sizeof(RecordId)+sizeof(int)
#define totalEntries getKeyCount()
#define availableSpace sizeof(buffer)-sizeof(PageId) // subtract PageId size for the pointer at the end of the node
#define takenSpace getKeyCount()*entrySize

// NONLEAF
#define nl_entrySize sizeof(PageId)+sizeof(int)
#define nl_takenSpace getKeyCount()*nl_entrySize
#define nl_availableSpace sizeof(buffer)-sizeof(PageId)
#define nl_totalEntries getKeyCount()


/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
	return pf.read(pid,buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */

RC BTLeafNode::write(PageId pid, PageFile& pf)
{ 
	// write the memory buffer to the disk page
    return pf.write(pid,buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
	return keys;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{ 	
    /*
     * If there is enough space in the buffer, locate the first
     * eid with a key larger than your key. If a key is found,
     * you must make room for your new entry by shifting the
     * entries to the right. If the new entry is to be inserted
     * at the end of the node, then skip the memmove step. Once
     * space has been created for your entry, insert it into buffer.
     * Increment key count.
     */
    
    // If there is space for it, insert entry
    if ( takenSpace + entrySize <= availableSpace ) {
        int eid = 0;        // entry id
        
        // Shifts the larger entries to the right one entrySize
        // note: memmove uses intermediate buffer, memcpy does not
        // First entry/pair has eid = 1
        // set eid to first entry >= key, returns 0 if found
		// if locate!=0 that means we place entry at end of our buffer (dont need to move entries to the right)
        if (locate(key,eid) == 0) {
        memmove(buffer+eid*entrySize,
               buffer+(eid-1)*entrySize,
               takenSpace-(eid-1)*entrySize);
        }
        
        // put my entry into a buffer
        char buf[entrySize];
        memset(buf,rid.pid,sizeof(rid.pid));
        memset(buf+sizeof(rid.pid),rid.sid,sizeof(rid.sid));
        memset(buf+sizeof(RecordId),key,sizeof(key));
        
        // insert the entry
        memcpy(buffer+(eid-1)*entrySize,
               buf, 
               sizeof(buf));

        keys++;
    }
    else {
        return RC_NODE_FULL;
    }
    
	return 0; 
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */

// NOTE: ADDED PARAMETER PageId siblingPid !!!!
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{ 
	// split first and get the siblingKey
    // compare siblingKey to key to be inserted
    // insert the key into either the current Leaf Node or the
    // sibling leaf node
    int new_eid;
    RC rc = locate(key,new_eid);

    int split_eid = totalEntries/2+1;
    
    int flag = 0;               // 0 = insert on left, 1 = insert on right
    if(new_eid > split_eid) { // want to insert into sibling on the right
        split_eid++;          // so leave one more entry on the left to balance
        flag = 1;
    }
    
    // Copy right side of the split to new node
    int size_left = (split_eid-1)*entrySize;
    int size_right = takenSpace - size_left;
    memcpy(sibling.buffer,
           buffer+size_left,
           size_right);
    
    // set new node's next pointer and this node's next pointer
  	// TODO: Check later, can do this in the index instead
 	/* int next_pid_offset = sizeof(buffer)-sizeof(PageId);
    memset(sibling.buffer+next_pid_offset,getNextNodePtr(),sizeof(PageId));
    memset(buffer+next_pid_offset, siblingPid, sizeof(PageId));
    */

    // Clean the contents of the original node
    memset(buffer+size_left,'\0',size_right);
    
    // Insert the new entry
    RC r;
    if (flag==1)  { // insert into right side
        r = sibling.insert(key,rid);
        sibling.keys = (size_right+entrySize)/entrySize;
    }
    else {  // insert into left side
        r = insert(key,rid);
        keys = (size_left+entrySize)/entrySize;
    }
    
    // Get the first key of the sibling
    char key_buf[sizeof(int)+1];
    memcpy(key_buf,sibling.buffer+sizeof(RecordId), sizeof(int));
    memset(key_buf+sizeof(int),'\0',1);
    siblingKey = atoi(key_buf);
    
	return r; 
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 
    /*
     * Loop through all of the current entries. Each iteration,
     * get the corresponding key and compare it to the search key.
     * If key>=searchKey then you've found your eid. If never found,
     * then that means there is no match. Set eid to end of the entries
     * and return RC_NO_SUCH_RECORD indicating no match.
     */
    
    // helper variables
   // int start_offset = sizeof(RecordId);    // Offset to first key
   // int nextKey_offset = sizeof(RecordId)+sizeof(int);  // Offset to next key value
    int key = 0;
    RecordId rid;
    int cur_eid;
    for (cur_eid=1; cur_eid <= totalEntries; cur_eid++) {
        if (readEntry(cur_eid,key,rid) == 0) {// readEntry returns 0 on success
            if (key >= searchKey) {
                eid = cur_eid;
                return 0;
            }
        }
    }
    // SearchKey is larger than all current keys
    // return eid to the eid after last spot (totalEntries+1)
    eid = cur_eid;
    return RC_NO_SUCH_RECORD;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
    /*
     * - Find the offsets to the eid structure and the key
     * - Put the sid,pid, and key char arrays into a buffer
     *   for conversion to int
     * - convert buffers to integers
     */
    if (eid>getKeyCount()) return RC_NO_SUCH_RECORD;
    
    // Get offsets to different values
    int offsetToRID_SID = (eid-1)*entrySize;
    int offsetToRID_PID = offsetToRID_SID+sizeof(PageId);
    int offsetToKey = offsetToRID_PID+sizeof(int);
    
    // rid.pid
    char rid_pid_buf[sizeof(PageId)+1];
    memcpy(rid_pid_buf,buffer+offsetToRID_PID, sizeof(PageId));
    memset(rid_pid_buf+sizeof(PageId),'\0',1);
    
    // rid.sid
    char rid_sid_buf[sizeof(int)+1];
    memcpy(rid_sid_buf,buffer+offsetToRID_SID, sizeof(int));
    memset(rid_sid_buf+sizeof(int),'\0',1);
    
    // key
    char key_buf[sizeof(int)+1];
    memcpy(key_buf,buffer+offsetToKey, sizeof(int));
    memset(key_buf+sizeof(int),'\0',1);
    
    // convert buffers to integers and return by reference
    rid.pid = atoi(rid_pid_buf);
    rid.sid = atoi(rid_sid_buf);
    key = atoi(key_buf);
    
    return 0; 
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{   
    int next_pid_offset = sizeof(buffer)-sizeof(PageId);
    
    char next_pid_buf[sizeof(PageId)+1]; 
    memcpy(next_pid_buf,buffer+next_pid_offset, sizeof(PageId));
    memset(next_pid_buf+sizeof(PageId),'\0',1); 
    
    PageId pid = (PageId)atoi(next_pid_buf);
    return pid; 
}

/*
 * Set the pid of the next sibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 
    int next_pid_offset = sizeof(buffer)-sizeof(PageId);
    memset(buffer+next_pid_offset,(int)pid,sizeof(PageId));
    return 0; 
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf){ 
	return pf.read(pid,buffer); 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf){ 
	return pf.write(pid, buffer); 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount(){ 
	return keys; 
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid){ 
	/*
     * If there is enough space in the buffer, locate the first
     * eid with a key larger than your key. If a key is found,
     * you must make room for your new entry by shifting the
     * entries to the right. If the new entry is to be inserted
     * at the end of the node, then skip the memmove step. Once
     * space has been created for your entry, insert it into buffer.
     * Increment key count.
     */
    
    // If there is space for it, insert entry
    if ( nl_takenSpace + nl_entrySize <= nl_availableSpace ) {        
        // Shifts the larger entries to the right one entrySize
        // note: memmove uses intermediate buffer, memcpy does not
        // First entry/pair has eid = 1
        // set eid to first entry >= key, returns 0 if found
		// if locate!=0 that means we place entry at end of our buffer (dont need to move entries to the right)
        int eid = 0;        // entry id locate: @[IN] eid
        if (locate(key,eid) == 0) {
               memmove(buffer+eid*nl_entrySize,
               buffer+(eid-1)*nl_entrySize,
               nl_takenSpace-(eid-1)*nl_entrySize);
        }
        
        // put my entry into a buffer
        char buf[nl_entrySize];
        memset(buf,pid,sizeof(pid));
        memset(buf+sizeof(pid),key,sizeof(key));
        
        // insert the entry
        memcpy(buffer+(eid-1)*nl_entrySize,
               buf, 
               sizeof(buf));

        keys++;
    }
    else {
        return RC_NODE_FULL;
    }
    
	return 0;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{ 
	// split first and get the siblingKey
    // compare siblingKey to key to be inserted
    // insert the key into either the current Leaf Node or the
    // sibling leaf node
    
    int new_eid;
    RC rc = locate(key,new_eid);

    int split_eid = nl_totalEntries/2+1;
    
    int flag = 0;               // 0 = insert on left, 1 = insert on right
    if(new_eid > split_eid) { // want to insert into sibling on the right
        split_eid++;          // so leave one more entry on the left to balance
        flag = 1;
    }
    //
    // Copy right side of the split to new node
    int size_left = (split_eid-1)*nl_entrySize;
    int size_right = nl_takenSpace - size_left;
    memcpy(sibling.buffer,
           buffer+size_left,
           size_right);
    
    // set new node's next pointer and this node's next pointer
	// TODO: Check later, up to us whether we do this here or in index
    /*int next_pid_offset = sizeof(buffer)-sizeof(PageId);
    memset(sibling.buffer+next_pid_offset,getNextNodePtr(),sizeof(PageId));
    memset(buffer+next_pid_offset, siblingPid, sizeof(PageId));
    */

    // Clean the contents of the original node
    memset(buffer+size_left,'\0',size_right);
    
    // Insert the new entry and set # of keys
    RC r;
    if (flag==1)  { // insert into right side
        r = sibling.insert(key,pid);
        sibling.keys = (size_right+nl_entrySize)/nl_entrySize;
    }
    else {  // insert into left side
        r = insert(key,pid);
        keys = (size_left+nl_entrySize)/nl_entrySize;
    }
    
    // Get the first key of the sibling - same as the middle node to be pushed up
    char key_buf[sizeof(int)+1];
    memcpy(key_buf,sibling.buffer+sizeof(PageId), sizeof(int));
    memset(key_buf+sizeof(int),'\0',1);
    midKey = atoi(key_buf);

	// erase the midKey because it will be pushed up
	memmove(sibling.buffer,sibling.buffer+nl_entrySize,nl_takenSpace-nl_entrySize);
	sibling.keys--;
	memcpy(sibling.buffer+nl_takenSpace,'\0',nl_entrySize);
	
	return r;
	
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */

// HELPER FUNCTION
RC BTNonLeafNode::readEntry(int eid, int& key, PageId& pid)
{ 
    /*
     * - Find the offsets to the pid and key
     * - Put the pid and key char arrays into a buffer
     *   for conversion to int
     * - convert buffers to integers
     */
    if (eid>getKeyCount()) return RC_NO_SUCH_RECORD;

    // Get offsets to different values
    int offsetToPID = (eid-1)*nl_entrySize;
    int offsetToKey = offsetToPID+sizeof(int);

    // pid
    char pid_buf[sizeof(PageId)+1];
    memcpy(pid_buf,buffer+offsetToPID, sizeof(PageId));
    memset(pid_buf+sizeof(PageId),'\0',1);

    // key
    char key_buf[sizeof(int)+1];
    memcpy(key_buf,buffer+offsetToKey, sizeof(int));
    memset(key_buf+sizeof(int),'\0',1);

    // convert buffers to integers and return by reference
    pid = atoi(pid_buf);
    key = atoi(key_buf);

    return 0; 
}

// HELPER FUNCTION
RC BTNonLeafNode::locate(int searchKey, int& eid)
{ 
    /*
     * Loop through all of the current entries. Each iteration,
     * get the corresponding key and compare it to the search key.
     * If key>=searchKey then you've found your eid. If never found,
     * then that means there is no match. Set eid to end of the entries
     * and return RC_NO_SUCH_RECORD indicating no match.
     */

    int key = 0;
    int cur_eid = 0;
    int cur_pid = 0;
    for (cur_eid=1; cur_eid <= nl_totalEntries; cur_eid++) {
        if (readEntry(cur_eid,key,cur_pid) == 0) {// readEntry returns 0 on success
            if (key >= searchKey) {
                eid = cur_eid;
                return 0;
            }
        }
    }
    // SearchKey is larger than all current keys
    // return eid to the eid after last spot (totalEntries+1)
    eid = cur_eid;
	return RC_NO_SUCH_RECORD;
}

 /**
    * Given the searchKey, find the child-node pointer to follow and
    * output it in pid.
    * @param searchKey[IN] the searchKey that is being looked up.
    * @param pid[OUT] the pointer to the child node to follow.
    * @return 0 if successful. Return an error code if there is an error.
    */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{ 
    // find the first key that is bigger than my search key
    // then return the pointer right before it
    // if it is the biggest key, it'll return the last eid
    // and still be the correct pointer
    
    int eid = 0;
    int key = 0;
    if (locate(searchKey, eid)==0) {
        // get the pointer to the left of the first key that was found
        // to be larger than your key
        readEntry(eid, key, pid);
    }
    else {
        // find the last eid and get its right pointer
        char pid_buf[sizeof(PageId)+1];
        memcpy(pid_buf,buffer+nl_takenSpace, sizeof(PageId));
        memset(pid_buf+sizeof(PageId),'\0',1);
        pid = atoi(pid_buf);
    }
    return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{ 
    memset(buffer,pid1,sizeof(PageId));
    memset(buffer+sizeof(PageId),key,sizeof(int));
    memset(buffer+nl_entrySize,pid2,sizeof(PageId));
    return 0;
}
